public class Practice3 {
    //https://leetcode.cn/problems/vvXgSW/description/
    //合并有序链表用递归实现, 昨天用堆实现
    public ListNode mergeSort(ListNode[] lists,int left,int right){
        if(left > right){
            return null;
        }
        if(left == right){
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode l1 = mergeSort(lists,left,mid);
        ListNode l2 = mergeSort(lists,mid + 1,right);

        return unionList(l1,l2);
    }
    public ListNode unionList(ListNode l1,ListNode l2){
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode head = new ListNode(-1);
        ListNode cur3 = head;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur3.next = cur1;
                cur1 = cur1.next;
                cur3 = cur3.next;
            }else{
                cur3.next = cur2;
                cur2 = cur2.next;
                cur3 = cur3.next;
            }
        }
        if(cur1 != null){
            cur3.next = cur1;
        }
        if(cur2 != null){
            cur3.next = cur2;
        }
        return head.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSort(lists,0,lists.length - 1);
    }
}
